/*
 * Copyright (C) 2011 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.collect.BoundType.CLOSED;
import static com.google.common.collect.BoundType.OPEN;

import com.google.common.annotations.GwtCompatible;
import com.google.common.base.Objects;
import java.io.Serializable;
import java.util.Comparator;
import javax.annotation.Nullable;

/**
 * A generalized interval on any ordering, for internal use. Supports {@code null}. Unlike
 * {@link Range}, this allows the use of an arbitrary comparator. This is designed for use in the
 * implementation of subcollections of sorted collection types.
 *
 * <p>
 * Whenever possible, use {@code Range} instead, which is better supported.
 *
 * @author Louis Wasserman
 */
@GwtCompatible(serializable = true)
final class GeneralRange<T> implements Serializable {
    /**
     * Converts a Range to a GeneralRange.
     */
    static <T extends Comparable> GeneralRange<T> from(Range<T> range) {
        @Nullable
        T lowerEndpoint = range.hasLowerBound() ? range.lowerEndpoint() : null;
        BoundType lowerBoundType = range.hasLowerBound() ? range.lowerBoundType() : OPEN;

        @Nullable
        T upperEndpoint = range.hasUpperBound() ? range.upperEndpoint() : null;
        BoundType upperBoundType = range.hasUpperBound() ? range.upperBoundType() : OPEN;
        return new GeneralRange<T>(Ordering.natural(), range.hasLowerBound(), lowerEndpoint, lowerBoundType,
                range.hasUpperBound(), upperEndpoint, upperBoundType);
    }

    /**
     * Returns the whole range relative to the specified comparator.
     */
    static <T> GeneralRange<T> all(Comparator<? super T> comparator) {
        return new GeneralRange<T>(comparator, false, null, OPEN, false, null, OPEN);
    }

    /**
     * Returns everything above the endpoint relative to the specified comparator, with the
     * specified endpoint behavior.
     */
    static <T> GeneralRange<T> downTo(Comparator<? super T> comparator, @Nullable T endpoint, BoundType boundType) {
        return new GeneralRange<T>(comparator, true, endpoint, boundType, false, null, OPEN);
    }

    /**
     * Returns everything below the endpoint relative to the specified comparator, with the
     * specified endpoint behavior.
     */
    static <T> GeneralRange<T> upTo(Comparator<? super T> comparator, @Nullable T endpoint, BoundType boundType) {
        return new GeneralRange<T>(comparator, false, null, OPEN, true, endpoint, boundType);
    }

    /**
     * Returns everything between the endpoints relative to the specified comparator, with the
     * specified endpoint behavior.
     */
    static <T> GeneralRange<T> range(Comparator<? super T> comparator, @Nullable T lower, BoundType lowerType,
            @Nullable T upper, BoundType upperType) {
        return new GeneralRange<T>(comparator, true, lower, lowerType, true, upper, upperType);
    }

    private final Comparator<? super T> comparator;
    private final boolean hasLowerBound;
    @Nullable
    private final T lowerEndpoint;
    private final BoundType lowerBoundType;
    private final boolean hasUpperBound;
    @Nullable
    private final T upperEndpoint;
    private final BoundType upperBoundType;

    private GeneralRange(Comparator<? super T> comparator, boolean hasLowerBound, @Nullable T lowerEndpoint,
            BoundType lowerBoundType, boolean hasUpperBound, @Nullable T upperEndpoint, BoundType upperBoundType) {
        this.comparator = checkNotNull(comparator);
        this.hasLowerBound = hasLowerBound;
        this.hasUpperBound = hasUpperBound;
        this.lowerEndpoint = lowerEndpoint;
        this.lowerBoundType = checkNotNull(lowerBoundType);
        this.upperEndpoint = upperEndpoint;
        this.upperBoundType = checkNotNull(upperBoundType);

        if (hasLowerBound) {
            comparator.compare(lowerEndpoint, lowerEndpoint);
        }
        if (hasUpperBound) {
            comparator.compare(upperEndpoint, upperEndpoint);
        }
        if (hasLowerBound && hasUpperBound) {
            int cmp = comparator.compare(lowerEndpoint, upperEndpoint);
            // be consistent with Range
            checkArgument(cmp <= 0, "lowerEndpoint (%s) > upperEndpoint (%s)", lowerEndpoint, upperEndpoint);
            if (cmp == 0) {
                checkArgument(lowerBoundType != OPEN | upperBoundType != OPEN);
            }
        }
    }

    Comparator<? super T> comparator() {
        return comparator;
    }

    boolean hasLowerBound() {
        return hasLowerBound;
    }

    boolean hasUpperBound() {
        return hasUpperBound;
    }

    boolean isEmpty() {
        return (hasUpperBound() && tooLow(getUpperEndpoint())) || (hasLowerBound() && tooHigh(getLowerEndpoint()));
    }

    boolean tooLow(@Nullable T t) {
        if (!hasLowerBound()) {
            return false;
        }
        T lbound = getLowerEndpoint();
        int cmp = comparator.compare(t, lbound);
        return cmp < 0 | (cmp == 0 & getLowerBoundType() == OPEN);
    }

    boolean tooHigh(@Nullable T t) {
        if (!hasUpperBound()) {
            return false;
        }
        T ubound = getUpperEndpoint();
        int cmp = comparator.compare(t, ubound);
        return cmp > 0 | (cmp == 0 & getUpperBoundType() == OPEN);
    }

    boolean contains(@Nullable T t) {
        return !tooLow(t) && !tooHigh(t);
    }

    /**
     * Returns the intersection of the two ranges, or an empty range if their intersection is empty.
     */
    GeneralRange<T> intersect(GeneralRange<T> other) {
        checkNotNull(other);
        checkArgument(comparator.equals(other.comparator));

        boolean hasLowBound = this.hasLowerBound;
        @Nullable
        T lowEnd = getLowerEndpoint();
        BoundType lowType = getLowerBoundType();
        if (!hasLowerBound()) {
            hasLowBound = other.hasLowerBound;
            lowEnd = other.getLowerEndpoint();
            lowType = other.getLowerBoundType();
        } else if (other.hasLowerBound()) {
            int cmp = comparator.compare(getLowerEndpoint(), other.getLowerEndpoint());
            if (cmp < 0 || (cmp == 0 && other.getLowerBoundType() == OPEN)) {
                lowEnd = other.getLowerEndpoint();
                lowType = other.getLowerBoundType();
            }
        }

        boolean hasUpBound = this.hasUpperBound;
        @Nullable
        T upEnd = getUpperEndpoint();
        BoundType upType = getUpperBoundType();
        if (!hasUpperBound()) {
            hasUpBound = other.hasUpperBound;
            upEnd = other.getUpperEndpoint();
            upType = other.getUpperBoundType();
        } else if (other.hasUpperBound()) {
            int cmp = comparator.compare(getUpperEndpoint(), other.getUpperEndpoint());
            if (cmp > 0 || (cmp == 0 && other.getUpperBoundType() == OPEN)) {
                upEnd = other.getUpperEndpoint();
                upType = other.getUpperBoundType();
            }
        }

        if (hasLowBound && hasUpBound) {
            int cmp = comparator.compare(lowEnd, upEnd);
            if (cmp > 0 || (cmp == 0 && lowType == OPEN && upType == OPEN)) {
                // force allowed empty range
                lowEnd = upEnd;
                lowType = OPEN;
                upType = CLOSED;
            }
        }

        return new GeneralRange<T>(comparator, hasLowBound, lowEnd, lowType, hasUpBound, upEnd, upType);
    }

    @Override
    public boolean equals(@Nullable Object obj) {
        if (obj instanceof GeneralRange) {
            GeneralRange<?> r = (GeneralRange<?>) obj;
            return comparator.equals(r.comparator) && hasLowerBound == r.hasLowerBound
                    && hasUpperBound == r.hasUpperBound && getLowerBoundType().equals(r.getLowerBoundType())
                    && getUpperBoundType().equals(r.getUpperBoundType())
                    && Objects.equal(getLowerEndpoint(), r.getLowerEndpoint())
                    && Objects.equal(getUpperEndpoint(), r.getUpperEndpoint());
        }
        return false;
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(comparator, getLowerEndpoint(), getLowerBoundType(), getUpperEndpoint(),
                getUpperBoundType());
    }

    private transient GeneralRange<T> reverse;

    /**
     * Returns the same range relative to the reversed comparator.
     */
    GeneralRange<T> reverse() {
        GeneralRange<T> result = reverse;
        if (result == null) {
            result = new GeneralRange<T>(Ordering.from(comparator).reverse(), hasUpperBound, getUpperEndpoint(),
                    getUpperBoundType(), hasLowerBound, getLowerEndpoint(), getLowerBoundType());
            result.reverse = this;
            return this.reverse = result;
        }
        return result;
    }

    @Override
    public String toString() {
        return comparator + ":" + (lowerBoundType == CLOSED ? '[' : '(') + (hasLowerBound ? lowerEndpoint : "-\u221e")
                + ',' + (hasUpperBound ? upperEndpoint : "\u221e") + (upperBoundType == CLOSED ? ']' : ')');
    }

    T getLowerEndpoint() {
        return lowerEndpoint;
    }

    BoundType getLowerBoundType() {
        return lowerBoundType;
    }

    T getUpperEndpoint() {
        return upperEndpoint;
    }

    BoundType getUpperBoundType() {
        return upperBoundType;
    }
}
